package com.zxy.leetcode._00000_00099._00010_00019;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/4sum/
 *
 * 四数之和
 * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，
 * 判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值
 * 与 target 相等？找出所有满足条件且不重复的四元组。
 *
 * 注意：答案中不可以包含重复的四元组。
 *
 * 思路：双指针
 * 参考三数之和 Test00015
 */
public class Test00018 {

    public static void main(String[] args) {
        Test00018 test = new Test00018();

        int[] nums = {1, 0, -1, 0, -2, 2};
        System.out.println(test.fourSum(nums, 0));
        System.out.println(test.fourSum(nums, -2));
        System.out.println(test.fourSum(nums, 2));
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums == null || nums.length < 4) {
            return Collections.emptyList();
        }

        Arrays.sort(nums);

        List<List<Integer>> list = new ArrayList<>(nums.length / 4);

        for (int i=0; i<=nums.length-4; i++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }

            for (int j=i+1; j<=nums.length-3; j++) {
                if (j > i+1 && nums[j] == nums[j-1]) {
                    continue;
                }

                int l = j + 1;
                int r = nums.length - 1;
                while (l < r) {
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum == target) {
                        List<Integer> tmpList = new ArrayList<>();
                        tmpList.add(nums[i]);
                        tmpList.add(nums[j]);
                        tmpList.add(nums[l]);
                        tmpList.add(nums[r]);
                        list.add(tmpList);

                        // 去除重复的数据
                        while (l < r && nums[l] == nums[l+1]) l++;
                        while (l < r && nums[r] == nums[r-1]) r--;

                        r --;
                        l ++;
                    }else if (sum > target) {
                        r --;
                    }else {
                        l ++;
                    }
                }
            }

        }

        return list;
    }

}
